/*
 * @lc app=leetcode id=460 lang=cpp
 *
 * [460] LFU Cache
 */
class LFUCache {
public:
    LFUCache(int capacity)
        : cap(capacity), minF(1), size(0) {
    }
    
    int get(int key) {

        if (kToVF.find(key) == kToVF.end()) {
            return -1;
        }

        int val  = kToVF[key].first;
        int freq = kToVF[key].second; 

        // incr freq of key
        kToVF[key].second++;

        // remove key key from freq's list
        fToKList[freq].erase(kToListIter[key]);

        // remove old key's Iter and add new one
        kToListIter.erase(key);

        // then push_back key into new list
        freq++;
        fToKList[freq].push_back(key);

        // add key's Iter 
        kToListIter[key] = --fToKList[freq].end();

        if (fToKList[minF].size() < 1) {
            minF++;
        }
        return val;
    }
    
    void put(int key, int value) {
        if (cap == 0) {
            return ;
        }

        if (get(key) != -1) {
            kToVF[key].first = value;
            return ;
        }

        if (size == cap) {
            kToVF.erase(fToKList[minF].front());
            kToListIter.erase(fToKList[minF].front());
            fToKList[minF].pop_front();
            size--;
        }

        kToVF[key] = std::make_pair(value, 1);
        fToKList[1].push_back(key);
        kToListIter[key] = --fToKList[1].end();

        minF = 1;
        size++;
    }
private:
    map<int, std::pair<int,int>> kToVF;
    map<int, std::list<int>::iterator> kToListIter;
    map<int, std::list<int>> fToKList;
    int size, cap;
    int minF;
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

